Balance and Transitivity

SNA Week 5

Matt Pietryka

Calculating Bonacich Power Centrality

\[ c_i(\alpha, \beta) = \sum_j (\alpha + \beta c_j)s_{ij} \]

where:

\(c_j\) is node \(j\)’s score
\(s_{ij}\) is cell \(i,j\) in the sociomatrix
\(\alpha\) a scaling parameter
\(\beta\) determines the role of node \(j\)’s score

# CREATE RANDOM NETWORK 
N_NODES <- 20
set.seed(2)
er_net <- erdos.renyi.game(N_NODES, p = 0.2, directed = FALSE)
er_net <- er_net  %>%  add_layout_(with_fr())

# CALCULATE POWER CENTRALITY
library(igraph)
power_centrality(er_net,  exponent = -1)

##  [1]  0.48099187  1.60330622  0.18037195  0.56115718  1.36281029
##  [6]  0.96198373  0.22045461  0.98202506  1.96405012 -0.10020664
## [11]  0.26053726 -0.04008266  1.44297560  0.46095054  1.66343020
## [16]  0.06012398  0.74152913 -0.78161178  1.20247966  1.20247966

power_centrality(er_net,  exponent = 1)

##  [1] -0.7290826 -0.7290826 -0.5468120  0.1822707 -0.3645413 -1.2758946
##  [7]  0.3645413  0.0000000 -0.9113533 -0.5468120 -0.9113533 -1.6404359
## [13] -1.2758946 -0.1822707 -0.3645413 -2.1872478 -0.3645413 -0.7290826
## [19] -1.4581652 -1.6404359

Note: Node labels represent power rank; Node opacity indicates relative differences in power

Balance

Balance measures help us understand triples in signed networks

triples are triads of actors
Signed networks denote relationships of opposing valences

Signed networks denote relationships of opposing valences

edges in signed networks typically have one of two values: +1 or -1
- friend vs enemy
- agree vs disagree
- love vs hate
- ally vs opponent

All possible connected triples

Creating example networks

library(igraph)
library(tidyverse)

N_NODES <- 8

# ------- CREATE BALANCED NETWORK  ---------------- #

# DATA ON EDGES
edge_data <- expand.grid(a = 1:N_NODES, b = 1:N_NODES)   %>%
  filter(a != b)  %>%
  mutate(a_group = ifelse(a < 6, 1, 2))  %>%
  mutate(b_group = ifelse(b < 6, 1, 2))  %>%
  mutate(weight = ifelse(a_group == b_group, 1, -1))  %>%
  mutate(sign = ifelse(a_group == b_group, "+", "-"))

Creating example networks

edge_vector <- rbind(edge_data[,1], edge_data[,2])  %>% c()
balanced_net <- graph(edges = edge_vector, n = N_NODES, directed = FALSE)

# VERTEX ATTRIBUTES
  V(balanced_net)$color        <- "grey50"
  V(balanced_net)$size         <- 35
  V(balanced_net)$label.cex    <- 3
  V(balanced_net)$label.font   <- 2
  V(balanced_net)$label.family <- "sans"
  V(balanced_net)$label.color  <- "white"
  V(balanced_net)$frame.color  <- NA

Creating example networks

# EDGE ATTRIBUTES
  E(balanced_net)$weight <- edge_data$weight
  E(balanced_net)$sign   <- edge_data$sign
  E(balanced_net)$color  <- ifelse(edge_data$weight > 0, 
                                  "grey80", 
                                  shade_B0)
  E(balanced_net)$lty    <- ifelse(E(balanced_net)$weight > 0, 
                                1, 
                                2)
  E(balanced_net)$width  <- 2

Creating example networks

# ------- CREATE UNBALANCED NETWORK  ---------------- #

set.seed(400)
unbalanced_net <- graph(edges = edge_vector, 
                         n = N_NODES, 
                         directed = FALSE) 
# VERTEX ATTRIBUTES
  V(unbalanced_net)$color        <- "grey30"
  V(unbalanced_net)$size         <- 35
  V(unbalanced_net)$label.cex    <- 3
  V(unbalanced_net)$label.font   <- 2
  V(unbalanced_net)$label.family <- "sans"
  V(unbalanced_net)$label.color  <- "white"
  V(unbalanced_net)$frame.color  <- NA

Creating example networks

# EDGE ATTRIBUTES
  E(unbalanced_net)$weight <- sample(c(-1,1), 
                                      ecount(unbalanced_net),
                                      replace = TRUE)
  E(unbalanced_net)$sign   <- ifelse(E(unbalanced_net)$weight > 0, 
                                     "+", 
                                     "-")
  E(unbalanced_net)$color  <- ifelse(E(unbalanced_net)$weight > 0, 
                                    "grey80", 
                                    shade_B0)
  E(unbalanced_net)$lty    <- ifelse(E(unbalanced_net)$weight > 0, 
                                  1, 
                                  2)
  E(unbalanced_net)$width  <- 2

Creating example networks

#=============================================
#   CREATE PLOTS
#=============================================

# LAYOUTS
balanced_lay_circle   <- layout_(balanced_net, in_circle())
unbalanced_lay_circle <- layout_(unbalanced_net, in_circle())

Creating example networks

# PLOTTING PREFERENCES
par(mar = c(0, 0, 0, 0)) # NO MARGINS ON ANY SIDE
par(mfrow = c(1, 2)) #  ONE ROW AND TWO COLUMNS
par(cex.main = 4) # PLOT TITLE SIZE

# ------- PLOT WITHOUT HIGHLIGHTS  ---------------- #
plot(balanced_net, layout = balanced_lay_circle)
title(main = "A", line = -4)
plot(unbalanced_net, layout = unbalanced_lay_circle)
title(main = "B", line = -4)

What differences do you see?

Creating example networks

# FIND COMMUNITIES
balanced_coms   <- spinglass.community(balanced_net, 
                                       implementation = "neg")
unbalanced_coms <- spinglass.community(unbalanced_net, 
                                       implementation = "neg")

# PLOTTING PREFERENCES
par(mar = c(0, 0, 0, 0)) # NO MARGINS ON ANY SIDE
par(mfrow = c(1, 2)) #  ONE ROW AND TWO COLUMNS
par(cex.main = 4) # PLOT TITLE SIZE

# ------- PLOT WITH HIGHLIGHTS  ---------------- #
plot(balanced_net,  mark.groups = balanced_coms,
     layout = balanced_lay_circle,
     mark.border = NA,
     mark.col = c(shade_A1,shade_C1))
title(main = "A", line = -4)

plot(unbalanced_net,  mark.groups = unbalanced_coms,
     layout = unbalanced_lay_circle,
     mark.border = NA,
     mark.col = adjustcolor(c(shade_A2, shade_B2, shade_C2), 0.8))
title(main = "B", line = -4)

Balance of triples: positive product when multiplying links of three connected nodes

Balanced if \(s_{ij} \times s_{jk} \times s_{ki} = 1\)
- Balanced with even number of negative edges
Unbalanced if \(s_{ij} \times s_{jk} \times s_{ki} = -1\)
- Balanced with odd number of negative edges

#=============================================
#   FUNCTION TO FIND SIGN OF EACH TRIPLE IN NETWORK
# (ASSUMES SIGN OF TIES IS STORED IN 'E(g)$weight')
#=============================================
triple_signs <- function(net) {
  #FIND IDS OF ALL NODES IN EACH TRIPLE
    triple_ids <- combn(1:vcount(net), 3)
  #FOR EACH TRIPLE ...
  apply(triple_ids, 2,  function(x) {
    # ... IDENTIFY ITS EDGES
    edges <- E(net) [ x %--% x ]
    # ... IDENTIFY EDGE VALUES
    weights <- E(net)[edges]$weight
    # ... FIND PRODUCT OF ITS VALUES
    sign <- prod(weights)
    # RETURN THE SIGN OF EACH VALUE
    return(sign)
  })
}

triple_signs(balanced_net)  %>% table()

## .
##  1 
## 56

triple_signs(unbalanced_net) %>% table()

## .
## -1  1 
## 36 20

Balance of nodes: all cycles containing node \(i\) are positive

Also known as local balance
Cycles are paths originating and returning to the same node
The sign of a cycle is the product of its links

#=============================================
#   FUNCTION TO FIND LOCAL BALANCE FOR EACH NODE 
# (ASSUMES COMPLETE GRAPH)
# (ASSUMES SIGN OF TIES IS STORED IN 'E(g)$weight')
#=============================================
local_balance <- function(net) {
 # FIND ALL TRIPLES IN 'g'
  triple_ids <- combn(1:vcount(net), 3)
 # INDICATE RELEVANT TRIPLES FOR EACH NODE
  rel_triple <- apply(triple_ids, 2, function(x) V(net) %in% x)
 # FIND SIGN OF EACH TRIPLE
  signs <- triple_signs(net)
 # TOTAL TRIPLES NODE i IS INVOLVED IN
  total_trips <- apply(rel_triple, 1,sum)
 # TOTAL NUMBER OF POSITIVE TRIPLES NODE i IS INVOLVED IN
  pos_trips <- sapply(V(net), function(x)  sum(signs[rel_triple[x, ]] > 0))
 # LOCAL BALANCE
  return(pos_trips/total_trips)
}

local_balance(balanced_net)

## [1] 1 1 1 1 1 1 1 1

local_balance(unbalanced_net)

## [1] 0.3333333 0.2380952 0.5714286 0.5238095 0.2857143 0.2380952 0.3809524
## [8] 0.2857143

Balance of network: network is balanced iff all triangles are balanced

If balanced, all nodes can be divided into two subsets
All links within subsets must be positive
All links between subsets must be negative

Balance of network: network is balanced iff all triangles are balanced

If balanced, all nodes can be divided into two subsets
All links within subsets must be positive
All links between subsets must be negative

Degree of balance in network: the proportion of all triangles that are positive

\[ B = \frac{C^+}{(C^+ + C^-)} \]

Where:

\(C^+\) = number of positive triangles
\(C^-\) number of negative triangles

\[ B = \frac{C^+}{(C^+ + C^-)} \]

#=============================================
#   FUNCTION TO FIND GLOBAL NETWORK BALANCE 
# (ASSUMES SIGN OF TIES IS STORED IN 'E(g)$weight')
#=============================================

network_balance <- function(g) {
  # FIND ALL TRIPLES IN 'g'
  triples <- combn(1:vcount(g), 3)
  # SET COUNTERS TO ZERO
  good <- bad <- 0
  # FOR EACH TRIPLE, DETERMINE IF BALANCED
  for (t in 1:ncol(triples)) {
    # THE FOCAL TRIPLE
    tri <- triples[,t]
    # FIND ALL EDGES IN FOCAL TRIPLE
    edges <- E(g) [ tri %--% tri ]
    if (length(unique(get.edges(g, edges))) < 3) { next }
    if (prod(E(g)[edges]$weight) > 0) {
      good <- good + 1 # IF PRODUCT IS POSITIVE INCREMENT UP
    } else {
      bad <- bad + 1   # IF PRODUCT IS NEGATIVE INCREMENT UP
    }
  }
  # CALCULATE GLOBAL BALANCE
  b <- good/(good + bad)
  # IS THE NETWORK BALANCED?
  is_balanced <- ifelse(b == 1, TRUE, FALSE)
  # RETURN RESULTS AS LIST
  list(is_balanced, n_balanced = good, n_unbalanced = bad, global_balance = b)
}

network_balance(balanced_net)

## [[1]]
## [1] TRUE
## 
## $n_balanced
## [1] 56
## 
## $n_unbalanced
## [1] 0
## 
## $global_balance
## [1] 1

network_balance(unbalanced_net)

## [[1]]
## [1] FALSE
## 
## $n_balanced
## [1] 20
## 
## $n_unbalanced
## [1] 36
## 
## $global_balance
## [1] 0.3571429

local_balance(unbalanced_net)  %>% mean()

## [1] 0.3571429

Degree of balance in network: the proportion of all triangles that are positive

# FIND BALANCE LEVEL
network_balance(g)

## [[1]]
## [1] FALSE
## 
## $n_balanced
## [1] 20
## 
## $n_unbalanced
## [1] 20
## 
## $global_balance
## [1] 0.5

Transitivity

The Transitivity of a triad means that when there is a tie from \(i\) to \(j\), and also from \(j\) to \(k\), then there is also a tie from \(i\) to \(k\)

If \(i \nrightarrow j\) and/or \(j \nrightarrow k\), then the triad is vacuously transitive
neither transitive nor intransitive

If \(S^2_{ik} \geq 1\), the relation is transitive if \(s_{ik} = 1\)

Transitivity of the network given by the Global Clustering Coefficient C

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}}\]

Closed triples are three nodes connected by three undirected ties
Open triples are three nodes connected by two undirected ties
Gives the probability that two nodes with a common partner are adjacent to each other

# CREATE NETWORK

N_NODES <- 4
edges <- c(1,2, 1,3, 2,3, 3, 4)
trans_net <- graph(edges = edges, n = N_NODES, directed = FALSE)  %>% 
  set_vertex_attr("name", value = letters[1:N_NODES])



#PLOT NETWORK
set.seed(1)
plot(trans_net, 
     vertex.size = 60,
     vertex.frame.color = NA,
     vertex.color = shade_C0, 
     vertex.label.color = "white",
     vertex.label.cex = 5,
     vertex.label.family = "sans",
     edge.width = 3)

Transitivity of the network given by the Global Clustering Coefficient C

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}}\]

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}} \]

# NETWORK AS A SOCIOMATRIX
trans_socio <- get.adjacency(trans_net, sparse = FALSE)

# SECOND- AND THIRD-ORDER SOCIOMATRICES
p2 <- trans_socio %*% trans_socio
p3 <- p2 %*% trans_socio


# PATHS OF LENGTH TWO (IGNORING PATHS TO SELF)
diag(p2) <- 0
p2_sum <- sum(p2)
p2_sum

## [1] 10

# CYCLES OF LENGTH THREE 
c3_sum <- diag(p3)   %>% sum()
c3_sum

## [1] 6

# GLOBAL CLUSTERING
c3_sum/p2_sum

## [1] 0.6

\[ C = \frac{\text{number of cycles of length three}}{\text{number of paths of length two}} \]

# GLOBAL CLUSTERING BY HAND
c3_sum/p2_sum

## [1] 0.6

# GLOBAL CLUSTERING IN IGRAPH 
transitivity(trans_net, type = "globalundirected")

## [1] 0.6

RANDOM_N <- 50

# CREATE AN ERDOS-RENYI SMALL WORLD NETWORK
set.seed(1)
er_net <- erdos.renyi.game(RANDOM_N, p = 0.1, directed = FALSE)
edge_density(er_net)

## [1] 0.09877551

transitivity(er_net, type = "globalundirected")

## [1] 0.1125

RANDOM_N <- 50

# CREATE A WATTS-STROGATZ SMALL WORLD NETWORK
set.seed(1)
ws_net <- sample_smallworld(1, RANDOM_N, 2, 0.10) 
edge_density(ws_net)

## [1] 0.08163265

transitivity(ws_net, type = "globalundirected")

## [1] 0.245283

Transitivity of the nodes given by the Local Clustering Coefficient \(c_i\)

\[ c_i = \frac{\text{number of ties in i's neighborhood}}{\text{possible number of ties in i's neighborhood| neighborhood size }} \]

# BY HAND
lapply(1:N_NODES,  function(x){
  # FIND ONE-STEP NEIGHBORHOODS
  local_ids <- which(trans_socio[x, ] == 1)
  nhood   <- trans_socio[local_ids, local_ids]
  # TOTAL NUMBER OF NEIGHBORS
  n_neighbors <- nrow(nhood)
  # MAXIMUM NUMBER OF TIES IN NEIGHBORHOOD
  nhood_max   <- n_neighbors * (n_neighbors - 1)
  # LOCAL CLUSTERING = (NUM. TIES/MAX POSSIBLE NUM. TIES)
  sum(nhood)/nhood_max
  })

## [[1]]
## [1] 1
## 
## [[2]]
## [1] 1
## 
## [[3]]
## [1] 0.3333333
## 
## [[4]]
## numeric(0)

\[ c_i = \frac{\text{number of ties in i's neighborhood}}{\text{possible number of ties in i's neighborhood| neighborhood size }} \]

# IN IGRAPH
transitivity(trans_net, type = "localundirected")

## [1] 1.0000000 1.0000000 0.3333333       NaN